\section{Problema 1}

\subsection{Introducción}

El  objetivo de este trabajo es implementar cuatro heurísticas para el algoritmo de Dijkstra.
Se las aplicará en un problema de \textit{pathfinding}. Luego se analizará y compararán las soluciones a las que llega cada una, para determinar en qué situaciones
es conveniente una u otra.

\paragraph{}
Se modelará un mapa rectangular utilizando un grafo dirigido.

\begin{itemize}
	\item Los nodos representan casillas
	\item Las aristas representan la dirección de tránsito desde una casilla (el extremo de salida) hasta otra adyacente (el extremo de llegada)
\end{itemize}

\paragraph{}
Además cumple los siguientes invariantes:
\begin{enumerate}
	\item No se consideran adyacentes las casillas que están en contacto por una esquina (i.e. en diagonal una respecto de la otra)
	\item No hay \textit{warparound} en el mapa. Es decir, no puede llegarse a una casilla que está sobre una misma fila o columna, yendo únicamente en el sentido contrario.
	\item El grado de salida máximo que puede tener una casilla es la cantidad de casillas adyacentes.
\end{enumerate}


\paragraph{}
\subsection{Análisis de Complejidad}

El mapa tiene un total de $X*Y$ casillas. Ese será el tamaño de entrada, y lo llamaremos N.

\paragraph{ TAD Mapa }
\paragraph{ }

La complejidad espacial $s(X,Y)$ es $\Omega(f(X,Y))$, porque el mapa está almacenado en una matriz, de estructuras de tamaño acotado, de $X*Y$.

Fuera de eso, sólo tiene variables primitivas.

En total la complejidad espacial es $\Theta(N)$

Todas las funciones tiene complejidad temporal $O(1)$ porque devuelven el contenido de variables primitivas, y su acceso es constante.

En particular, la función establecerRestriccion realiza una cantidad acotada de pasos, y escribe en una posición específica de un vector (según la STL, es constante).

Y la función $adyacentes()$ devuelve una lista de adyacencias, que es a lo sumo 4. O bien, con una cota más ajustada, el grado del nodo. En cualquier caso es $O(1)$.



\subsubsection{Dijkstra}

\paragraph{Complejidad espacial}

\begin{itemize}
	\item vector$<$float$>$ $distancias$ : $X*Y$ números en coma flotante. Complejidad: $O(N)$
	\item set$<$unsigned int$>$ $Q$:  alcanza un total de $X*Y$ elementos. Complejidad: $O(N)$
	\item Los punteros $predecesores$ y $recorrido$, tiene costo $O(1)$, pero una vez reservado el espacio. Apuntan a una estructura de tamaño $X*Y$.
	Complejidad: $O(N)$
	\item list$<$unsigned int$>$ $n_adyacentes$ tiene a lo sumo 4 elementos. Complejidad: $O(1)$
\end{itemize}

\textbf{Complejidad espacial total:} $O(N)$


\paragraph{Complejidad temporal}

Será explicada a partir de la implementación.

\begin{itemize}
\item \textbf{Fragmento 1}:

\begin{verbatim}
    bool alcanzado = false;
    unsigned int w = M->Ancho();
    unsigned int h = M->Alto();
    unsigned int SIZE = w*h;

    set<unsigned int>::iterator it;
    list<unsigned int>::iterator itl;	

    unsigned int poslineal_ini = inicio.x * w + inicio.y;
    unsigned int poslineal_dest = destino.x * w + destino.y;
	
    unsigned int u=SIZE, v;
\end{verbatim}

Cada paso tiene complejidad $O(1)$, según el modelo uniforme (es importante aclararlo, porque hay multiplicaciones).

\item \textbf{Fragmento 2}:

\begin{verbatim}
    distancias.clear();
    distancias.resize(w*h, INFINITO);
    Q.clear();
    vector<unsigned int>* predecesores = new vector<unsigned int> (h*w, SIZE);
    vector<vector<unsigned char> >* recorrido = new vector< vector<unsigned char> > (h, vector<unsigned char>(w,NO_EXPLORADO) );
\end{verbatim}
Según la STL, redimensionar un vector ($resize$) y crear ($new$) uno de tamaño $N = w*h$ tiene costo $O(N)$, con $N$ la cantidad de casillas.


\item \textbf{Fragmento 3}:
\begin{verbatim}
    distancias[poslineal_ini] = 0;
    (*predecesores)[poslineal_ini] = poslineal_ini; 
    (*recorrido)[inicio.x][inicio.y] = SOLUCION
    list<unsigned int> n_adyacentes;
\end{verbatim}
Estas son operaciones con costo $O(1)$

\item \textbf{Fragmento 4}:

\begin{verbatim}
    for(unsigned int i = 0; i < SIZE; i++)
        Q.insert(i);
\end{verbatim}
Se realizan SIZE (es decir, $N$) inserciones. Cada una tiene complejidad $O(log$ (Q.size)), pero asintóticamente es $O(log N)$.

Ese ciclo tiene complejidad $O(N log N)$.

\item \textbf{Fragmento 5}:

\begin{verbatim}
    while( !Q.empty() )
    {
        //...
    }
\end{verbatim}

El ciclo se itera $N$ veces, que es la cantidad de elementos (la cantidad de nodos) que alcanzará a contener Q.

A continuación, el análisis de complejidad del cuerpo del ciclo en cada iteración.

\item \textbf{Fragmento 5a}:
\begin{verbatim}
        u = *(Q.begin());
        Q.erase(Q.begin());
\end{verbatim}
La primera operación tiene costo $O(1)$ (por la STL).
La segunda, $erase$ tiene complejidad $O(log$ (Q.size)). Una vez que se extrae un nodo de Q, no se lo vuelve a agregar.

\item \textbf{Fragmento 5b}:
\begin{verbatim}
    if ((*M).direcciones(u / (*M).Ancho(),u % (*M).Ancho()) == FULL_RESTRIC)
        break;
    if (u == poslineal_dest)
        alcanzado = true;
\end{verbatim}
Ambas comparaciones tienen costo $O(1)$. La complejidad de la función $direcciones()$ es $O(1)$.

\item \textbf{Fragmento 5c}:
\begin{verbatim}
    else {
        n_adyacentes = (*M).adyacentes(u);
        for(itl = n_adyacentes.begin(); itl != n_adyacentes.end(); itl++) {
            if (distancias[*itl] > distancias[u] + (*M).tiempo(u)) {
                it = Q.find(*itl);
                v = *it;
					
                Q.erase(it);					
                distancias[*itl] = distancias[u] + (*M).tiempo(u);				
                Q.insert(v);
					
               (*recorrido)[*itl / (*M).Ancho()][*itl % (*M).Ancho()] = VISITADO;
               (*predecesores)[*itl] = u;
            }
         }
     }
\end{verbatim}
$adyacentes()$ devuelve una lista de casillas a las que se puede desplazar (en su forma lineal\footnote{La forma lineal de la casilla (0,0) es 0. Para las demás, es la posición desde (0,0) si las filas fueras contiguas. Es decir, (x,y) se escribe x*ANCHO + y, suponiendo que x indexe las filas}.
La longitud de la lista está acotada por 4.

En el ciclo \textbf{for}: para cada adyacente al nodo extraído, se evalúa si la distancia de su predecesor (el valor del vector $predecesor$ en la posición lineal) más el tiempo de transito es menor que la distancia encontrada hasta el momento (en el vector $distancias$).

Si es falso, continúa. Y la complejidad es $O(1)$.

Si es verdadero, realiza operaciones de complejidad $O(log$ Q.size): find, erase e insert.
Asintóticamente es del orden de $O(log N)$.

La complejidad total del \textbf{ciclo} en el peor caso es $N * ( O(log N) + 4 * O(log N) )$  = $O( N log N)$


\item \textbf{Fragmento 6}: Marcar la solución en vector de tamaño $N$
\begin{verbatim}
    if (alcanzado){
        v = poslineal_dest;
        while ((*predecesores)[v] != v) {
            (*recorrido)[v / (*M).Ancho()][v % (*M).Ancho()] = SOLUCION;
            v = (*predecesores)[v];
        }
    }    
\end{verbatim}

Si no hubo solución, por la comparación el costo es $O(1)$

Caso contrario, marca todos los nodos en una matriz, que forman parte del camino que une el nodo inicial con el final.
En el peor caso, se debe recorrer todos los nodos. Es decir, $O(N)$.

\item \textbf{Fragmento 7}: Mostrar la solución
\begin{verbatim}
    mostrarSolucion(recorrido);
	
    delete predecesores;
    delete recorrido;
\end{verbatim}
Imprimir la solución encontrada, en pantalla, tiene complejidad $O(N)$ porque debe recorrer toda la matriz de $X*Y$ y realizar 1 escritura en pantalla por cada una.

La misma complidad tiene $delete$ sobre un puntero a vector de enteros.


\end{itemize}

\paragraph{Complejidad total}
La complejidad total es $O(N log N)$


\begin{verbatim}
\end{verbatim}

\subsubsection{A$^*$}

\paragraph{Complejidad espacial}

\begin{itemize}
	\item vector$<$float$>$ $distancias$ : $X*Y$ números en coma flotante. Complejidad: $O(N)$
	\item set$<$unsigned int$>$ $Q$:  alcanza un total de $X*Y$ elementos. Complejidad: $O(N)$
	\item Los punteros $predecesores$ y $recorrido$, tiene costo $O(1)$, pero una vez reservado el espacio. Apuntan a una estructura de tamaño $X*Y$.
	Complejidad: $O(N)$
	\item list$<$unsigned int$>$ $n\_adyacentes$ tiene a lo sumo 4 elementos. Complejidad: $O(1)$
\end{itemize}

\paragraph{}
Y además, se agrega un vector de tamaño $N$, $heuristicas\_X$, en el que se almacenan números en coma flotante.

Tanto la heurística con distancias euclideanas, como con distancias Manhattan, y las dos restantes, usan un vector del mismo tamaño. En lugar de la letra X van cuatro caracteres que identifican a la heurística.


\textbf{Complejidad espacial total:} $O(N)$

\paragraph{Complejidad temporal}

Es la misma que la implementación anterior, porque se usan las mismas estructuras, excepto quizá un vector más.

Pero dentro del ciclo sólo se agregan operaciones con costo $O(1)$, como son las comparaciones, y asignaciones de estructuras de tamaño acotado (casilla, por ej.)




\subsubsection{Decisiones de implementación}

La  implementación es la misma en las cuatro heurísticas. Tan sólo cambia la función H.
El vector $heuristicas\_X$ contiene el valor de H($x$), en la posición $x$, según la heurística $X$.


\paragraph{}
Se utilizó la clase \textbf{set} de la STL, para que cumpla la función de heap binario.

Cada heurística tiene asociado una estructura, y definida una función que compara dos enteros. Esa comparación es la que usa la estructura subyacente de \textbf{set} para
ordenar los elementos.
Y equivale a la función F(x).

\paragraph{}
La función begin() devuelve un iterador a un elemento, que coincide con el menor según el ordenamiento establecido, en $O(1)$. Como en un min-heap.

Para mantener el invariante de heap, si es necesario actualizar su distancia, lo buscamos y eliminamos. Eso tiene complejidad $O(log (N))$. Modificamos la distancia en un vector, $O(1)$,
y lo volvemos a insertar.

El propio set se encargará de ubicarlo en la posición que deba utilizando la nueva distancia como dato para comparar.




\subsubsection{Heurísticas y análisis}

Las dos heurísticas implementadas, son:

\begin{enumerate}
	\item Dar preferencia a aquellos nodos que están más cerca de una línea imaginaria que une la casilla inicial con la casilla destino.
	\item Multiplicar el resultado de alguna de las funciones heurísticas por una constante mayor que 1.
\end{enumerate}

La primera se comporta mejor en casos en los que se puede llegar a la casilla final siguiendo una trayectoria casi alineada a la distancia euclidea, que sería la ideal
si no la cantidad de direcciones por casilla fuera prácticamente infinita.

Con la heurística con distancias Manhattan, hay problemas entre menos alineadas a columnas o filas se encuentren las casillas, porque existen muchos caminos con distancia Manhattan de longitud $k$ (podemos referirnos al tema de combinatoria, bosones).

De modo similar, con distancias euclideanas.

\begin{verbatim}
50 50
0 0
49 49
0 0
50 50
25 0
25 49
0 0
\end{verbatim}
Comparamos utilizando esos casos de prueba, en un mapa sin restricciones.
Y esto fue lo que obtuvimos:

